#include <vector>

using namespace std;
class Solution
{
public:
    // 思路： 二分查找
    // 把二维矩阵看成一维数组进行二分查找
    // 怎么获取二维矩阵的行和列：row = mid / n, col = mid % n
    // 为什么这样计算：假设矩阵有 n 列，那么每增加 n 个元素就会换到下一行
    //                col = mid % n 是因为每行有 n 列，取模可以得到当前元素在该行的位置
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        if (matrix.empty() || matrix[0].empty())
            return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0;          // 一维数组的起始位置
        int right = m * n - 1; // 一维数组的结束位置
        while (left <= right)
        {
            int mid = left + (right - left) / 2; // 防止溢出
            int row = mid / n;                   // 计算行号
            int col = mid % n;                   // 计算列号
            if (target == matrix[row][col])
                return true;
            else if (target > matrix[row][col])
                left = mid + 1;
            else
                right = mid - 1;
        }
        return false;
    }
};